//
//  StringSolution.hpp
//  leetcode
//
//  Created by Ellie on 2021/1/31.
//  Copyright © 2021 Ellie. All rights reserved.
//

#ifndef StringSolution_hpp
#define StringSolution_hpp

#include <stdio.h>
#include <string>
#include <queue>
#include <unordered_map>
#include <stack>
#include <vector>
#include <deque>
#include <iostream>
#include <sstream>

using namespace std;

class StringSolution
{
public:
    // 28. 实现 strStr()
    int strStr(string haystack, string needle);
    // 242. 有效的字母异位词
    bool isAnagram(string s, string t);
    // 49. 字母异位词分组
    vector<vector<string>> groupAnagrams(vector<string>& strs);
    // 125. 验证回文串
    bool isPalindrome(string s);
    // 680. 验证回文字符串 Ⅱ
    // 删除右侧测试一次，删除左侧测试一次即可，记录左右然后回退一次过程
    bool validPalindrome(string s);
    // 266. 回文排列 如果没有指定输入限制，直接使用hashtable保存计数，如果说明字符可以用vector<int>(26,0);
    // 字符数量为128，也可以直接使用128大小的vector
    // 给定一个字符串，判断该字符串中是否可以通过重新排列组合，形成一个回文字符串。
    bool canPermutePalindrome(string s);
    // 267. 回文排列 II 给定一个字符串 s ，返回其通过重新排列组合后所有可能的回文字符串，并去除重复的组合。
    vector<string> generatePalindromes(string s);
    // 409. 最长回文串[构造最长的回文的字符个数，直接计算奇数即可，不用枚举]
    int longestPalindrome(string s);
    // 438. 找到字符串中所有字母异位词
    vector<int> findAnagrams(string s, string p);
    // 567. 字符串的排列 和438类似的解题思路
    bool checkInclusion(string s1, string s2);
    // 316. 去除重复字母 单调栈+去重复
    string removeDuplicateLetters(string s);
};

#endif /* StringSolution_hpp */
